package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/6/15 22:35
 */
public class LongestUnivaluePath_687 {

    private int path = 0;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return path;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        // 当左子树有值与根节点相同，则沿着左子节点向下，深度+1；右子树同理
        int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
        int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
        // 需要加上两端的路径，因为没有说是从上往下的，起点和终点的位置不固定
        path = Math.max(path, leftPath + rightPath);
        return Math.max(leftPath, rightPath);
    }

}
